#include <bits/stdc++.h>

using namespace std;

// 矩阵中和能被 K 整除的路径
// 给一个下标从0开始的 n * m 整数矩阵 grid 和一个整数 k
// 从起点(0,0)出发，每步只能往下或者往右，你想要到达终点(m-1, n-1)
// 请你返回路径和能被 k 整除的路径数目
// 由于答案可能很大，返回答案对10^9+7取余的结果
// 测试链接 : https://leetcode.cn/problems/paths-in-matrix-whose-sum-is-divisible-by-k/

class Solution 
{
public:
    const int MOD = 1e9 + 7;

    int numberOfPaths1(vector<vector<int>>& grid, int k) 
    {
        int m = grid.size(), n = grid[0].size();
        return f1(grid, m, n, k, 0, 0, 0);
    }

	// 当前来到(i,j)位置，最终一定要走到右下角(n-1,m-1)
	// 从(i,j)出发，最终一定要走到右下角(n-1,m-1)，有多少条路径，累加和%k的余数是r
    int f1(vector<vector<int>>& grid, int m, int n, int k, int i, int j, int r)
    {
        if(i == m - 1 && j == n - 1)
        {
            return grid[i][j] % k == r ? 1 : 0;
        }

        // 后续需要凑出来的余数need
        int need = (k + r - (grid[i][j] % k)) % k;
        int ans = 0;
        if(i + 1 < m) ans += f1(grid, m, n, k, i + 1, j, need);
        if(j + 1 < n) ans = (ans + f1(grid, m, n, k, i, j + 1, need)) % MOD;
        return ans;
    }

    int numberOfPaths2(vector<vector<int>>& grid, int k) 
    {
        int m = grid.size(), n = grid[0].size();
        vector<vector<vector<int>>> dp(m, vector<vector<int>>(n, vector<int>(k, -1)));
        return f2(grid, m, n, k, 0, 0, 0, dp);
    }

    int f2(vector<vector<int>>& grid, int m, int n, int k, int i, int j, int r, vector<vector<vector<int>>>& dp)
    {
        if(i == m - 1 && j == n - 1)
        {
            return grid[i][j] % k == r ? 1 : 0;
        }

        if(dp[i][j][r] != -1) return dp[i][j][r];

        // 后续需要凑出来的余数need
        int need = (k + r - (grid[i][j] % k)) % k;
        int ans = 0;
        if(i + 1 < m) ans += f2(grid, m, n, k, i + 1, j, need, dp);
        if(j + 1 < n) ans = (ans + f2(grid, m, n, k, i, j + 1, need, dp)) % MOD;
        dp[i][j][r] = ans;
        return ans;
    }

    int numberOfPaths3(vector<vector<int>>& grid, int k) 
    {
        int m = grid.size(), n = grid[0].size();
        int dp[m][n][k];
        memset(dp, 0, sizeof dp);
        dp[m - 1][n - 1][grid[m - 1][n - 1] % k] = 1;
        for(int i = m - 2; i >= 0; --i)
        {
            for(int r = 0; r < k; ++r)
            {
                dp[i][n - 1][r] = dp[i + 1][n - 1][(k + r - (grid[i][n - 1] % k)) % k];
            }
        }
        for(int j = n - 2; j >= 0; --j)
        {
            for(int r = 0; r < k; ++r)
            {
                dp[m - 1][j][r] = dp[m - 1][j + 1][(k + r - (grid[m - 1][j] % k)) % k];
            }
        }

        for(int i = m - 2; i >= 0; --i)
        {
            for(int j = n - 2; j >= 0; --j)
            {
                for(int r = 0; r < k; ++r)
                {
                    int need = (k + r - (grid[i][j] % k)) % k;
                    dp[i][j][r] = dp[i + 1][j][need];
                    dp[i][j][r] = (dp[i][j][r] + dp[i][j + 1][need]) % MOD;
                }
            }
        }
        return dp[0][0][0];
    }
};

// 参考灵神的题解
class Solution 
{
public:
    int numberOfPaths(vector<vector<int>>& grid, int k) 
    {
        const int MOD = 1e9 + 7;
        int m = grid.size(), n = grid[0].size();
        int f[m + 1][n + 1][k];
        memset(f, 0, sizeof f);
        f[0][1][0] = 1;
        for(int i = 0; i < m; ++i)
        {
            for(int j = 0; j < n; ++j)
            {
                for(int v = 0; v < k; ++v)
                {
                    f[i + 1][j + 1][(v + grid[i][j]) % k] = (f[i + 1][j][v] + f[i][j + 1][v]) % MOD;
                }
            }
        }    
        return f[m][n][0];
    }
};